/*
 * @Author: 0x9DEFA478
 * @Date: 2025-09-09 21:44:53
 * @LastEditTime: 2025-09-14 21:50:30
 * @LastEditors: 0x9DEFA478
 * @Description: 
 * 
 */
#ifndef hTree_H_Tree_RedBlack_HPP_
#define hTree_H_Tree_RedBlack_HPP_
#include "./H_Tree.hpp"
#include "./H_Tree_RedBlack.h"


namespace H{

  namespace Tree{

    namespace Internal{

      template<typename TypeKey,typename TypeData
#if __cplusplus >= 202000L
        ,Concept::TypeCompare<TypeKey> Compare
#else
        ,typename Compare
#endif
      >
      struct TreeInterface_RedBlack{
        using TypeLL=H_TreeNode_RedBlack;
        using Node=NodeBase<TypeLL,TypeKey,TypeData>;

        static TypeLL* FirstFree(Node* tree)noexcept{return H_Tree_RedBlack_FirstFree(tree);}
        static TypeLL* NextFree(TypeLL* ll_node)noexcept{return H_Tree_RedBlack_NextFree(ll_node);}

        static FindInsertResult FindInsert(Node* tree,const TypeKey& Key,TypeLL** ReturnNode)noexcept{
          H_TreeNode* Parent;
          FindInsertResult r;

          r=FindInsertResult::InsertToRoot;

          if(tree==nullptr){
            *ReturnNode=nullptr;
            return r;
          }

          Parent=&static_cast<TypeLL*>(tree)->Node;

          Compare compare;
          for(;;){
            H_TreeNode* Next;
            TypeLL* parent;
            int res;

            parent=H_TreeNode_To_H_TreeNode_RedBlack(Parent);
            res=compare(*Node::ToKey(parent),Key);

            if(res==0){
              *ReturnNode=parent;
              return FindInsertResult::Exist;
            }

            if(res<0){
              Next=Parent->Right;
              if(Next==nullptr){
                *ReturnNode=parent;
                r=FindInsertResult::InsertToRight;
                break;
              }
            }else{
              Next=Parent->Left;
              if(Next==nullptr){
                *ReturnNode=parent;
                r=FindInsertResult::InsertToLeft;
                break;
              }
            }
            
            Parent=Next;
          }

          return r;
        }

        static void InsertTo(Node** tree,TypeLL* ll_node,TypeLL* ReturnNode,FindInsertResult findInsertResult)noexcept{
          TypeLL* root;

          if(*tree==nullptr){
            root=nullptr;
          }else{
            root=*tree;
          }

          H_Tree_RedBlack_InsertTo(&root,ll_node,ReturnNode,static_cast<int>(findInsertResult));
          *tree=static_cast<Node*>(root);
        }

        static void Remove(Node** tree,TypeLL* ll_node)noexcept{
          TypeLL* root=*tree;
          
          H_Tree_RedBlack_Remove(&root,ll_node);
          
          if(root==nullptr){
            *tree=nullptr;
          }else{
            *tree=static_cast<Node*>(root);
          }
        }

        static TypeLL* Find(Node* tree,const TypeKey& Key)noexcept{
          H_TreeNode* r;

          if(tree==nullptr){
            return nullptr;
          }

          r=&static_cast<TypeLL*>(tree)->Node;

          Compare compare;
          while(r!=nullptr){
            int res;
            TypeLL* i_node;

            i_node=H_TreeNode_To_H_TreeNode_RedBlack(r);

            res=compare(*Node::ToKey(i_node),Key);

            if(res==0){
              return i_node;
            }
            if(res<0){
              r=r->Right;
              continue;
            }
            r=r->Left;
          }

          return nullptr;
        }
        
        static TypeLL* FrontNode(Node* tree)noexcept{return H_Tree_RedBlack_FrontNode(tree);}
        static TypeLL* BackNode(Node* tree)noexcept{return H_Tree_RedBlack_BackNode(tree);}
        static TypeLL* Node_Forward(TypeLL* ll_node)noexcept{return H_Tree_RedBlack_Forward(ll_node);}
        static TypeLL* Node_Backward(TypeLL* ll_node)noexcept{return H_Tree_RedBlack_Backward(ll_node);}
        static void Node_Copy(TypeLL* ll_node,const TypeLL* ll_node_src)noexcept{return H_Tree_RedBlack_Node_Copy(ll_node,ll_node_src);}
        static TypeLL* Node_Left(TypeLL* ll_node)noexcept{return H_TreeNode_To_H_TreeNode_RedBlack(ll_node->Node.Left);}
        static TypeLL* Node_Right(TypeLL* ll_node)noexcept{return H_TreeNode_To_H_TreeNode_RedBlack(ll_node->Node.Right);}
        static void Node_SetLeft(TypeLL* ll_node,TypeLL* ll_node_left)noexcept{
          ll_node->Node.Left=&ll_node_left->Node;
          if(ll_node_left!=nullptr){
            ll_node_left->Node.Parent=&ll_node->Node;
          }
        }
        static void Node_SetRight(TypeLL* ll_node,TypeLL* ll_node_right)noexcept{
          ll_node->Node.Right=&ll_node_right->Node;
          if(ll_node_right!=nullptr){
            ll_node_right->Node.Parent=&ll_node->Node;
          }
        }

      };

    }

    template<typename TypeKey,typename TypeData
#if __cplusplus >= 202000L
      ,Internal::Concept::TypeCompare<TypeKey> Compare=Internal::TypeCompare
      ,Concept::allocator Allocator=AllocatorDefault
#else
      ,typename Compare=Internal::TypeCompare
      ,typename Allocator=AllocatorDefault
#endif
    >
    using RedBlack=Internal::TreeBase<H_TreeNode_RedBlack,TypeKey,TypeData
      ,Allocator
      ,Internal::TreeInterface_RedBlack<TypeKey,TypeData,Compare>
    >;

  }

}


#endif //hTree_H_Tree_RedBlack_HPP_
